package com.jinan.algorithm.Backtrace;

import com.jinan.common.ListNode;
import com.jinan.common.TreeNode;

import java.util.*;

public class BackTraceTest {
    // 回溯三问
    // 1.当前操作？
    // 2.子问题？
    // 3.下一个子问题？
    public static void main(String[] args) {

    }

    // 数字和字母的映射
    private static final String[] NUMBER_MAP = {
            "", // 0
            "", // 1
            "abc", // 2
            "def", // 3
            "ghi", // 4
            "jkl", // 5
            "mno", // 6
            "pqrs", // 7
            "tuv", // 8
            "wxyz" // 9
    };

    /**
     * 17. 电话号码的字母组合 <a href="https://leetcode-cn.com/problems/letter-combinations-of-a-phone-number/">...</a>
     * 难度: 中等
     * tag: 哈希表 字符串 回溯
     * description:
     * 给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。
     * restriction:
     * 0 <= digits.length <= 4
     * digits[i] 是范围 ['2', '9'] 的一个数字。
     *
     * @param digits 输入的数字串
     * @return List<String> ans 所有能表示的字母组合
     * @apiNote 思路: 回溯
     */
    public List<String> letterCombinations(String digits) {
        List<String> ans = new ArrayList<>();
        if (digits.isEmpty()) {
            return ans;
        }
        backtrace(digits, 0, new StringBuilder(), ans);
        return ans;
    }

    public void backtrace(String digits, int index, StringBuilder sb, List<String> ans) {
        // 边界条件,如果索引超出了字符串的长度,说明已经遍历到了叶子节点,将当前路径加入到结果集中,并返回
        if (index == digits.length()) {
            ans.add(sb.toString());
            return;
        }
        // 非边界情况
        // 1.当前操作: 枚举当前索引对应的字符
        // 2.子问题: 构造长度为索引index的字符串
        // 3.下一个子问题: 构造长度为索引index+1的字符串，递归调用backtrace函数,传入下一个索引和当前路径
        // 4.返回: 如果索引超出了字符串的长度,说明已经遍历到了叶子节点,将当前路径加入到结果集中,并返回
        char c = digits.charAt(index);
        for (int i = 0; i < NUMBER_MAP[c - '0'].length(); i++) {
            sb.append(NUMBER_MAP[c - '0'].charAt(i));
            backtrace(digits, index + 1, sb, ans);
            // 恢复现场
            sb.deleteCharAt(sb.length() - 1);
        }
    }

    /**
     * 78. 子集 <a href="https://leetcode-cn.com/problems/subsets/">...</a>
     * 难度: 中等
     * tag: 数组 回溯
     * description:
     * 给定一组不含重复元素的整数数组 nums，返回该数组所有可能的子集（幂集）。
     * 说明：解集不能包含重复的子集。
     * restriction:
     * 1 <= nums.length <= 10
     * -10 <= nums[i] <= 10
     *
     * @param nums 输入的整数数组
     * @return List<List < Integer>> ans 所有可能的子集
     * @apiNote 思路: 子集型的回溯,两种做法：
     * 1.从输入角度，对于每个元素，都有选和不选的两种选择，就分成了两个分支，叶子节点是答案，所以回溯的递归深度为nums.length
     * 2.从答案角度，枚举第一个元素选什么，然后枚举第二个元素选什么，依次类推，每个节点是n叉分支，每个节点都是答案，回溯的递归深度为nums.length
     */
    public List<List<Integer>> subsets(int[] nums) {
        List<List<Integer>> ans = new ArrayList<>();
        List<Integer> path = new ArrayList<>();
        if (nums.length == 0) {
            return ans;
        }
        backtrace(nums, 0, path, ans);
        return ans;
    }

    // 输入角度的回溯
    public void backtrace(int[] nums, int index, List<Integer> path, List<List<Integer>> ans) {
        if (index == nums.length) {
            ans.add(new ArrayList<>(path));
            return;
        }
        // 不选num[index]
        backtrace(nums, index + 1, path, ans);
        // 选num[index]
        path.add(nums[index]);
        backtrace(nums, index + 1, path, ans);
        // 恢复现场
        path.remove(path.size() - 1);
    }

    // 答案角度的回溯
    public void backtrace2(int[] nums, int index, List<Integer> path, List<List<Integer>> ans) {
        ans.add(new ArrayList<>(path));
        for (int i = index; i < nums.length; i++) {
            path.add(nums[i]);
            backtrace2(nums, i + 1, path, ans);
            path.remove(path.size() - 1);
        }
    }

    /**
     * 131. 分割回文串 <a href="https://leetcode-cn.com/problems/palindrome-partitioning/">...</a>
     * 难度: 中等
     * tag: 回溯
     * description:
     * 给定一个字符串 s，将 s 分割成一些子串，使每个子串都是回文串。
     * 返回 s 所有可能的分割方案。
     * restriction:
     * 1 <= s.length <= 16
     * s 仅由小写英文字母组成
     *
     * @param s 输入的字符串
     * @return List<List < String>> ans 所有可能的分割方案
     * @apiNote 思路: 回溯，1.输入角度 枚举所有分割的分割点是否选择，判断分割点是否为回文串，如果是，则继续枚举下一个分割点，否则跳过当前分割点，继续枚举下一个分割点
     * 2.答案角度 枚举选择的分割点，判断分割点是否为回文串，如果是，则继续枚举下一个分割点，否则跳过当前分割点，继续枚举下一个分割点
     */
    public List<List<String>> partition(String s) {
        List<List<String>> ans = new ArrayList<>();
        if (s.isEmpty()) {
            return ans;
        }
        partition(s, 0, 0, new ArrayList<>(), ans);
        return ans;
    }

    // 输入角度的回溯
    private void partition(String s, int i, int start, ArrayList<String> path, List<List<String>> ans) {
        if (i == s.length()) {
            ans.add(new ArrayList<>(path));
            return;
        }
        if (i < s.length() - 1) {
            partition(s, i + 1, start, path, ans);
        }
        if (isPalindrome(s.substring(start, i + 1))) {
            path.add(s.substring(start, i + 1));
            partition(s, i + 1, i + 1, path, ans);
            path.remove(path.size() - 1);
        }
    }

    // 判断s是否为回文串
    public boolean isPalindrome(String s) {
        int left = 0;
        int right = s.length() - 1;
        while (left < right) {
            if (s.charAt(left) != s.charAt(right)) {
                return false;
            }
            left++;
            right--;
        }
        return true;
    }

    // 答案角度的回溯,枚举字串的结束点也就是下一个分割点的位置
    private void partition2(String s, int i, ArrayList<String> path, List<List<String>> ans) {
        if (i == s.length()) {
            ans.add(new ArrayList<>(path));
            return;
        }
        for (int j = i; j < s.length(); j++) {
            if (isPalindrome(s.substring(i, j + 1))) {
                path.add(s.substring(i, j + 1));
                partition2(s, j + 1, path, ans);
                path.remove(path.size() - 1);
            }
        }
    }

    /**
     * 77. 组合 <a href="https://leetcode-cn.com/problems/combinations/">...</a>
     * 难度: 中等
     * tag: 数组 回溯
     * description:
     * 给定两个整数 n 和 k，返回 1 ... n 中所有可能的 k 个数的组合。
     * restriction:
     * 1 <= n <= 20
     * 1 <= k <= n
     *
     * @param n 输入的整数n
     * @param k 输入的整数k
     * @return List<List < Integer>> ans 所有可能的组合
     * @apiNote 思路: 回溯，从1到n中选择k个数，每个数只能选一次,Cn^k
     */
    public List<List<Integer>> combine(int n, int k) {
        List<List<Integer>> ans = new ArrayList<>();
        List<Integer> path = new ArrayList<>();
        if (n < k) {
            return ans;
        }
        combine(k, n, path, ans);
        return ans;
    }

    private void combine(int k, int i, List<Integer> path, List<List<Integer>> ans) {
        //无剪枝
//        if(path.size() == k){
//            ans.add(new ArrayList<>(path));
//            return;
//        }
//        for (int j = i; j <= n; j++) {
//            path.add(j);
//            combine(n, k, j + 1, path, ans);
//            path.remove(path.size() - 1);
//        }

        //剪枝
        int d = k - path.size();//还要选择d个数
        //选完了
        if (d == 0) {
            ans.add(new ArrayList<>(path));
            return;
        }
        //从大到小枚举，i为枚举的下标，即每次递归剩下i个数可选，如果剩余数小于要选的个数d，则剪枝
        for (int j = i; j >= d; j--) {
            path.add(j);
            combine(k, j - 1, path, ans);
            path.remove(path.size() - 1);
        }
    }

    /**
     * 216. 组合总和 III <a href="https://leetcode-cn.com/problems/combination-sum-iii/">...</a>
     * 难度: 中等
     * tag: 数组 回溯
     * description:
     * 找出所有相加之和为 n 的 k 个数的组合。组合中只允许含有 1 - 9 的正整数，并且每种组合中不存在重复的数字。
     * 说明：
     * 所有数字都是正整数。
     * 解集不能包含重复的组合。
     * restriction:
     * 1 <= k <= 9
     * 1 <= n <= 60
     *
     * @param k 输入的整数k
     * @param n 输入的整数n
     * @return List<List < Integer>> ans 所有可能的组合
     * @apiNote 思路: 回溯，从1到9中选择k个数，每个数只能选一次,C9^k
     */
    public List<List<Integer>> combinationSum3(int k, int n) {
        List<List<Integer>> ans = new ArrayList<>();
        List<Integer> path = new ArrayList<>();
        if (k > n) {
            return ans;
        }
        combinationSum3(k, 9, n, path, ans);
        return ans;
    }

    private void combinationSum3(int k, int i, int t, List<Integer> path, List<List<Integer>> ans) {
        int d = k - path.size();//还要选择d个数
        //剪枝 如果t<0或者t>((2*i-d+1)/2)则剪枝，t为剩下要凑的和，
        // 如果path中的和已经大于t，则剪枝，或者剩下的最大d个数的和（即i到i-d+1等差数列求和）小于t，不可能凑齐了则剪枝。
        if (t < 0 || t > ((2 * i - d + 1) * d / 2)) {
            return;
        }
        if (d == 0) {
            ans.add(new ArrayList<>(path));
            return;
        }
        for (int j = i; j >= d; j--) {
            path.add(j);
            combinationSum3(k, j - 1, t - j, path, ans);
            path.remove(path.size() - 1);
        }
    }

    /**
     * 22. 括号生成 <a href="https://leetcode-cn.com/problems/generate-parentheses/">...</a>
     * 难度: 中等
     * tag: 数组 回溯
     * description:
     * 数字 n代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。
     * restriction:
     * 1 <= n <= 8
     *
     * @param n 输入的整数n
     * @return List<String> ans 所有可能的组合
     * @apiNote 思路: 回溯，在2n个位置中选择放左括号还是右括号，将左括号和右括号的个数都为n，当成选与不选的问题
     */
    public List<String> generateParenthesis(int n) {
        List<String> ans = new ArrayList<>();
        StringBuilder path = new StringBuilder();
        generateParenthesis(n, 0, path, ans);
        return ans;
    }

    private void generateParenthesis(int n, int i, StringBuilder path, List<String> ans) {
        if (path.length() == 2 * n) {
            ans.add(path.toString());
            return;
        }
        // 选择 左括号 i为左括号个数
        if (i < n) {
            path.append("(");
            generateParenthesis(n, i + 1, path, ans);
            path.deleteCharAt(path.length() - 1);
        }
        // 选择 右括号
        if (path.length() - i < i) {
            path.append(")");
            generateParenthesis(n, i, path, ans);
            path.deleteCharAt(path.length() - 1);
        }
    }

    /**
     * 912. 排序数组 <a href="https://leetcode-cn.com/problems/sort-an-array/">...</a>
     * 难度: 中等
     * tag: 数组 排序
     * description:
     * 给你一个整数数组nums，请你将该数组升序排列。
     * restriction:
     * 1 <= nums.length <= 50000
     * -50000 <= nums[i] <= 50000
     *
     * @param nums 输入的整数数组
     * @return int[] ans 排序后的数组
     * @apiNote 思路: 排序
     */
    public int[] sortArray(int[] nums) {
//        //选择排序：每一轮选择最小元素交换到未排定部分的开头
//        int n = nums.length;
//        // 循环不变量：[0, i) 有序，且该区间里所有元素就是最终排定的样子
//        for (int i = 0; i < n - 1; i++){
//            // 选择区间 [i, len - 1] 里最小的元素的索引，交换到下标 i
//            int min = i;
//            for (int j = i + 1; j < n; j++){
//                if (nums[j] < nums[min]){
//                    min = j;
//                }
//            }
//            if (min != i){
//                int temp = nums[i];
//                nums[i] = nums[min];
//                nums[min] = temp;
//            }
//        }
//        return nums;
//        //优点：交换次数最少。
//        //「选择排序」看起来好像最没有用，但是如果在交换成本较高的排序任务中，就可以使用「选择排序」。

//        // 插入排序
//        int n = nums.length;
//        // 循环不变量：将 nums[i] 插入到区间 [0, i) 使之成为有序数组
//        for (int i = 1; i < n; i++) {
//            // 先暂存这个元素，然后之前元素逐个后移，留出空位
//            int temp = nums[i];
//            int j = i;
//            // 注意边界 j > 0
//            for (; j > 0 && temp < nums[j - 1]; j--) {
//                nums[j] = nums[j - 1];
//            }
//            nums[j] = temp;
//        }
//        return nums;
//        //由于「插入排序」在「几乎有序」的数组上表现良好，特别地，在「短数组」上的表现也很好。因为「短数组」的特点是：每个元素离它最终排定的位置都不会太远。为此，在小区间内执行排序任务的时候，可以转向使用「插入排序」。

//        //归并排序
//        int n = nums.length;
//        mergeSort(nums, 0, n - 1);
//        return nums;

        //快速排序
//        int n = nums.length;
//        quickSort(nums, 0, n - 1);
//        return nums;
        //计数排序
        int n = nums.length;
        int[] count = new int[100000 + 1];
        for (int num : nums) {
            count[num + 50000]++;
        }
        int j = 0;
        for (int i = 0; i < 100000 + 1; i++) {
            while (count[i] > 0) {
                nums[j++] = i - 50000;
                count[i]--;
            }
        }
        return nums;
    }

    private final Random random = new Random();

    public void quickSort(int[] nums, int left, int right) {
        if (left < right) {
            // 随机选择基准值
            int pivotIndex = randomPartition(nums, left, right);
            // 递归调用较小的子数组
            quickSort(nums, left, pivotIndex - 1);
            quickSort(nums, pivotIndex + 1, right);
        }
    }

    private int partition(int[] nums, int left, int right) {
        int pivot = nums[left];
        while (left < right) {
            // 从右向左找到第一个小于pivot的元素
            while (left < right && nums[right] >= pivot) {
                right--;
            }
            nums[left] = nums[right]; // 更新left位置的值

            // 从左向右找到第一个大于pivot的元素
            while (left < right && nums[left] <= pivot) {
                left++;
            }
            nums[right] = nums[left]; // 更新right位置的值
        }
        nums[left] = pivot; // 将pivot放到正确的位置
        return left;
    }

    private int randomPartition(int[] nums, int left, int right) {
        Random rand = new Random();
        int pivotIndex = rand.nextInt((right - left) + 1) + left;
        swap(nums, left, pivotIndex);
        return partition(nums, left, right);
    }

    private void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }

    private void mergeSort(int[] nums, int left, int right) {
        if (left == right) {
            return;
        }
        // 递归
        int mid = (left + right) >>> 1;
        int[] temp = new int[nums.length];
        mergeSort(nums, left, mid);
        mergeSort(nums, mid + 1, right);

        // 如果数组的这个子区间本身有序，无需合并
        if (nums[mid] <= nums[mid + 1]) {
            return;
        }

        // 将 nums[left..mid] 和 nums[mid+1..right] 合并
        if (right + 1 - left >= 0) System.arraycopy(nums, left, temp, left, right + 1 - left);
        int i = left, j = mid + 1;
        for (int k = left; k <= right; k++) {
            if (i > mid) {
                nums[k] = temp[j];
                j++;
            } else if (j > right) {
                nums[k] = temp[i];
                i++;
            } else if (temp[i] <= temp[j]) {
                nums[k] = temp[i];
                i++;
            } else {
                nums[k] = temp[j];
                j++;
            }
        }
    }

    /**
     * 215. 数组中的第K个最大元素 <a href="https://leetcode.cn/problems/kth-largest-element-in-an-array/">...</a>
     * 难度： 中等
     * tags: 数组、快速选择、分治、堆（优先队列）
     * description: 给定整数数组 nums 和整数 k，请返回数组中第 k 个最大的元素。
     * 注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。
     * restrictions:
     * 1 <= k <= nums.length <= 10^5
     * -10^4 <= nums[i] <= 10^4
     *
     * @param nums 数组
     * @param k    第 k 个最大元素
     * @return 第 k 个最大元素
     * @apiNote 快速选择, 时间复杂度 O(n)
     */
    public int findKthLargest(int[] nums, int k) {
        // 1. sort函数
//        Arrays.sort(nums);
//        return nums[nums.length - k];
        // 2. 快速选择
        int n = nums.length;
        int left = 0;
        int right = n - 1;
        int pivotIndex = randomPartition(nums, left, right);
        while (left <= right && pivotIndex != n - k) {
            // 随机选择基准值
            pivotIndex = randomPartition(nums, left, right);
            if (pivotIndex > n - k) {
                right = pivotIndex - 1;
            } else if (pivotIndex < n - k) {
                left = pivotIndex + 1;
            }
        }
        return nums[pivotIndex];
    }

    /**
     * 93. 复原 IP 地址 <a href="https://leetcode.cn/problems/restore-ip-addresses/">...</a>
     * 难度： 中等
     * tags: 字符串、回溯
     * description: 给定一个只包含数字的字符串 s ，用以表示一个 IP 地址，返回所有可能从 s 获得的 有效 IP 地址 。你可以按任何顺序返回答案。
     * 有效 IP 地址 正好由四个整数（每个整数位于 0 到 255 之间组成，且不能含有前导 0），整数之间用 '.' 分隔
     * restrictions:
     * 1 <= s.length <= 300
     * s 仅由数字组成
     *
     * @param s 字符串
     * @return 有效 IP 地址
     * @apiNote 回溯
     */
//    public List<String> restoreIpAddresses(String s) {
//        this.s = s;
//        if (s.length()< 4 || s.length() > 12) {
//            return ans;
//        }
//        backtrack(0, 0);
//        return ans;
//    }
//
//    private String s;
//    private final List<String> ans = new ArrayList<>();
//    private final List<String> path = new ArrayList<>();
//
//    private void backtrack(int begin, int count) {
//        if (count == 4){
//            if (begin == s.length()){
//                ans.add(String.join(".", path));
//                return;
//            }
//        }
//        if(s.length()-begin > 3*(4-count)){
//            return;
//        }
//        for (int i = begin; i< begin+3 &&i < s.length(); i++){
//            if (isValid(s.substring(begin, i + 1))){
//                path.add(s.substring(begin, i + 1));
//                backtrack(i + 1, count + 1);
//                path.removeLast();
//            }
//        }
//    }
//
//    private boolean isValid(String substring) {
//        return substring.length() <= 3 && (substring.length() <= 1 || substring.charAt(0) != '0') && Integer.parseInt(substring) <= 255;
//    }


    /**
     * 1971. 寻找图中是否存在路径 <a href="https://leetcode.cn/problems/find-if-path-exists-in-graph/">...</a>
     * 难度： 中等
     * tags: 图、深度优先搜索、广度优先搜索、并查集
     * description: 给你一个正整数 n ，表示一个 无向 完全图，其中节点编号从 0 到 n - 1 。同时给你一个二维整数数组 edges ，其中 edges[i] = [ai, bi]表示节点 ai 和 bi 之间有一条边。图不一定连通。
     * 你需要返回一个布尔值，判断图中是否存在从节点 source 开始，到节点 destination 结束的 有向 路径。
     * restrictions:
     * 1 <= n <= 10^5
     * 0 <= edges.length <= 10^5
     * edges[i].length == 2
     * 0 <= ai, bi <= n - 1
     * ai != bi
     * source != destination
     *
     * @param n           节点数量
     * @param edges       二维整数数组
     * @param source      起始节点
     * @param destination 结束节点
     * @return 是否存在从节点 source 开始，到节点 destination 结束的 有向 路径
     * @apiNote 并查集
     */
    public boolean validPath(int n, int[][] edges, int source, int destination) {
        int[] parent = new int[n];
        int[] level = new int[n];
        for (int i = 0; i < n; i++) {
            parent[i] = i;
            level[i] = 1;
        }
        // 遍历所有边，进行合并操作
        for (int[] edge : edges) {
            union(parent, level, edge[0], edge[1]);
        }
        return find(parent, source) == find(parent, destination);

    }

    public void union(int[] parent, int[] level, int x, int y) {
        int xParent = find(parent, x);
        int yParent = find(parent, y);
        if (xParent == yParent) {
            return;
        }
        if (level[xParent] > level[yParent]) {
            parent[yParent] = xParent;
        } else if (level[xParent] < level[yParent]) {
            parent[xParent] = yParent;
        } else if (level[xParent] == level[yParent]) {
            parent[yParent] = xParent;
            level[xParent]++;
            level[yParent]++;
        }
    }

    public int find(int[] parent, int x) {
        int y = x;
        while (parent[y] != y) {
            y = parent[y];
        }
        parent[x] = y;
        return y;
    }


    /**
     * 1367.二叉树中的链表 <a href="https://leetcode.cn/problems/linked-list-in-binary-tree/">...</a>
     * 难度： 中等
     * tags: 树、深度优先搜索、链表、二叉树
     * description: 如果在二叉树中，存在一条一直向下的路径，
     * 且每个点的数值恰好一一对应以 head 为首的链表中每个节点的值，那么请你返回 True ，否则返回 False 。
     * restrictions:
     * 二叉树和链表中的每个节点的值都满足 1 <= node.val <= 100 。
     * 链表包含的节点数目在 1 到 100 之间。
     * 二叉树包含的节点数目在 1 到 2500 之间。
     *
     * @param head 链表
     * @param root 二叉树
     * @return 是否存在一条一直向下的路径
     */
    public boolean isSubPath(ListNode head, TreeNode<Integer> root) {
        if (head == null) {
            return true;// 如果链表为空，则认为匹配成功
        }
        if (root == null) {// 如果树为空，则匹配失败
            return false;
        }
        // 检查当前节点开始是否匹配，或者左子树或右子树中是否存在匹配路径
        return isSub(head, root) || isSubPath(head, root.left) || isSubPath(head, root.right);
    }

    /**
     * 辅助函数，检查链表是否从当前树节点开始匹配
     *
     * @param head 链表的头节点
     * @param root 当前树的节点
     * @return 是否匹配
     */
    public boolean isSub(ListNode head, TreeNode<Integer> root) {
        if (head == null) {
            return true;// 如果链表为空，则认为匹配成功
        }
        if (root == null) {
            return false;// 如果树为空，则匹配失败
        }
        if (head.val == root.val) {
            return isSub(head.next, root.left) || isSub(head.next, root.right);
        } else return false;
    }


    /**
     * 572. 另一棵树的子树 <a href="https://leetcode.cn/problems/subtree-of-another-tree/">...</a><a href="https://leetcode.cn/problems/check-subtree-lcci/description/">...</a>
     * 难度： 简单
     * tags: 树、深度优先搜索、二叉树
     * description: 给你两棵二叉树 root 和 subRoot 。检验 root 中是否包含和 subRoot 具有相同结构和节点值的子树。如果存在，返回 true ；否则，返回 false 。
     * restrictions:
     * 二叉树中节点的数目范围是 [1, 2000]
     * -10^4 <= Node.val <= 10^4
     * -10^4 <= subRoot.val <= 10^4
     *
     * @param root    二叉树
     * @param subRoot 二叉树
     * @return 是否包含和 subRoot 具有相同结构和节点值的子树
     */
    public boolean isSubtree(TreeNode<Integer> root, TreeNode<Integer> subRoot) {
        if (subRoot == null) {
            return true;
        }
        if (root == null) {
            return false;
        }
        if (subTreeHegiht == 0) {
            this.subTreeHegiht = getHeight(subRoot);
        }
        if (getHeight(root) == this.subTreeHegiht && isSame(root, subRoot)) {
            return true;
        }
        return isSubtree(root.left, subRoot) || isSubtree(root.right, subRoot);
    }

    public int subTreeHegiht = 0;

    public int getHeight(TreeNode<Integer> root) {
        if (root == null) {
            return 0;
        }
        return Math.max(getHeight(root.left), getHeight(root.right)) + 1;
    }

    private boolean isSame(TreeNode<Integer> root, TreeNode<Integer> subRoot) {
        if (root == null || subRoot == null) {
            return root == subRoot;
        }
        if (root.val != subRoot.val) {
            return false;
        }
        return isSame(root.left, subRoot.left) && isSame(root.right, subRoot.right);
    }

    /**
     * 230. 二叉搜索树中第K小的元素 <a href="https://leetcode.cn/problems/kth-smallest-element-in-a-bst/">...</a>
     * 难度： 中等
     * tags: 树、深度优先搜索、二叉搜索树、二叉树
     * description:
     * 给定一个二叉搜索树的根节点 root ，和一个整数 k ，请你设计一个算法查找其中第k个最小元素（从 1 开始计数）。
     * restrictions:
     * 树中节点数目为 n
     * 1 <= k <= n <= 10^4
     * 0 <= Node.val <= 10^4
     *
     * @param root 二叉搜索树的根节点
     * @param k    第k个最小元素（从 1 开始计数）
     * @return int 第k个最小元素（从 1 开始计数）
     */
    public int kthSmallest(TreeNode<Integer> root, int k) {
        this.k = k;
        kthSmallestdfs(root);
        return ans;
    }

    private void kthSmallestdfs(TreeNode<Integer> root) {
        if (root == null) {
            return;
        }
        kthSmallestdfs(root.left);
        if (--k == 0) {
            ans = root.val;
            return;
        }
        kthSmallestdfs(root.right);
    }

    private int ans = 0;
    private int k = 0;

    /**
     * 114. 二叉树展开为链表 <a href="https://leetcode.cn/problems/flatten-binary-tree-to-linked-list/">...</a>
     * 难度： 中等
     * tags: 树、深度优先搜索、二叉树
     * description: 给你二叉树的根结点 root ，请你将它展开为一个单链表：
     * 展开后的单链表应该同样使用 TreeNode ，其中 right 子指针指向链表中下一个结点，而左子指针始终为 null 。
     * 展开后的单链表应该与二叉树 先序遍历 顺序相同。
     * restrictions:
     * 树中结点数在范围 [0, 2000] 内
     * -100 <= Node.val <= 100
     * 进阶：你可以使用原地算法（O(1) 额外空间）展开这棵树吗？
     *
     * @param root 二叉树的根结点
     */
    public void flatten(TreeNode<Integer> root) {
        if (root == null) {
            return;
        }
        flatten(root.left);
        flatten(root.right);
        TreeNode<Integer> left = root.left;
        TreeNode<Integer> right = root.right;
        root.left = null;
        root.right = left;
        while (left != null && left.right != null) {
            left = left.right;
        }
        if (left != null) {
            left.right = right;
        } else root.right = right;
    }

    /**
     * 105. 从前序与中序遍历序列构造二叉树 <a href="https://leetcode.cn/problems/construct-binary-tree-from-preorder-and-inorder-traversal/">...</a>
     * 难度： 中等
     * tags: 树、数组、哈希表、分治、二叉树
     * description:
     * 给定两个整数数组preorder 和 inorder，其中preorder 是二叉树的先序遍历， inorder是同一棵树的中序遍历，请构造二叉树并返回其根节点。
     * restrictions:
     * 1 <= preorder.length <= 3000
     * inorder.length == preorder.length
     * -3000 <= preorder[i], inorder[i] <= 3000
     * preorder和inorder均 无重复 元素
     * inorder 均出现在 preorder
     * preorder保证 为二叉树的前序遍历序列
     * inorder保证 为二叉树的中序遍历序列
     *
     * @param preorder 先序遍历
     * @param inorder  中序遍历
     * @return 二叉树的根节点
     */
    public TreeNode<Integer> buildTree(int[] preorder, int[] inorder) {
        return buildTreedfs(preorder, 0, preorder.length - 1, inorder, 0, inorder.length - 1);
    }

    private TreeNode<Integer> buildTreedfs(int[] preorder, int preleft, int preright, int[] inorder, int inleft, int inright) {
        if (preleft > preright || inleft > inright) {
            return null;
        }
        TreeNode<Integer> root = new TreeNode<>(preorder[preleft]);
        for (int i = inleft; i <= inright; i++) {
            if (inorder[i] == preorder[preleft]) {
                root.left = buildTreedfs(preorder, preleft + 1, preleft + i - inleft, inorder, inleft, i - 1);
                root.right = buildTreedfs(preorder, preleft + i - inleft + 1, preright, inorder, i + 1, inright);
                return root;
            }
        }
        return null;
    }


    /**
     * 437. 路径总和 III <a href="https://leetcode.cn/problems/path-sum-iii/">...</a>
     * 难度： 中等
     * tags: 树、深度优先搜索、哈希表、二叉树
     * description: 给定一个二叉树的根节点 root ，和一个整数 targetSum ，求该二叉树里节点值之和等于 targetSum 的 路径 的数目。
     * 路径 不需要从根节点开始，也不需要在叶子节点结束，但是路径方向必须是向下的（只能从父节点到子节点）。
     * restrictions:
     * 树中节点总数在范围 [0, 1000] 内
     * -10^9 <= targetSum <= 10^9
     *
     * @param root      二叉树的根节点
     * @param targetSum 路径总和
     * @return 路径总和
     */
    public int pathSum(TreeNode<Integer> root, int targetSum) {
        Map<Long, Integer> prefixSumCount = new HashMap<>();
        prefixSumCount.put(0L, 1);
        dfs(root, 0L, targetSum, prefixSumCount);
        return ans;
    }

    private void dfs(TreeNode<Integer> node, long currentSum, int targetSum, Map<Long, Integer> prefixSumCount) {
        if (node == null) {
            return;
        }
        currentSum += node.val;
        // 统计以当前节点为终点的有效路径数
        ans += prefixSumCount.getOrDefault(currentSum - targetSum, 0);
        // 更新当前前缀和的出现次数
        prefixSumCount.put(currentSum, prefixSumCount.getOrDefault(currentSum, 0) + 1);
        // 递归处理左右子树
        dfs(node.left, currentSum, targetSum, prefixSumCount);
        dfs(node.right, currentSum, targetSum, prefixSumCount);
        // 回溯，恢复前缀和计数
        prefixSumCount.put(currentSum, prefixSumCount.get(currentSum) - 1);
    }

    /**
     * 994. 腐烂的橘子 <a href="https://leetcode.cn/problems/rotting-oranges/">...</a>
     * 难度： 中等
     * tags: 广度优先搜索、数组、矩阵、图
     * description: 在给定的 m x n 网格 grid 中，每个单元格可以有以下三个值之一：
     * 值 0 代表空单元格；
     * 值 1 代表新鲜橘子；
     * 值 2 代表腐烂的橘子。
     * 每分钟，腐烂的橘子 周围 4 个方向上相邻 的新鲜橘子都会腐烂。
     * 返回 直到单元格中没有新鲜橘子为止所必须经过的最小分钟数。如果不可能，返回 -1 。
     * restrictions:
     * m == grid.length
     * n == grid[i].length
     * 1 <= m, n <= 10
     * grid[i][j] 仅为0、1或2
     *
     * @param grid 网格
     * @return 最小分钟数
     */
    public int orangesRotting(int[][] grid) {
        int m = grid.length, n = grid[0].length;
        int ans = 0;
        Queue<int[]> queue = new ArrayDeque<>();

        // 初始化腐烂橘子队列
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == 2) {
                    queue.offer(new int[]{i, j});
                }
            }
        }

        // BFS扩散过程
        while (!queue.isEmpty()) {
            int[] cur = queue.poll();
            int x = cur[0], y = cur[1];

            // 只处理新鲜橘子（值1）
            if (x - 1 >= 0 && grid[x - 1][y] == 1) {
                grid[x - 1][y] = grid[x][y] + 1;
                queue.offer(new int[]{x - 1, y});
            }
            if (x + 1 < m && grid[x + 1][y] == 1) {
                grid[x + 1][y] = grid[x][y] + 1;
                queue.offer(new int[]{x + 1, y});
            }
            if (y - 1 >= 0 && grid[x][y - 1] == 1) {
                grid[x][y - 1] = grid[x][y] + 1;
                queue.offer(new int[]{x, y - 1});
            }
            if (y + 1 < n && grid[x][y + 1] == 1) {
                grid[x][y + 1] = grid[x][y] + 1;
                queue.offer(new int[]{x, y + 1});
            }
        }

        // 检查剩余新鲜橘子并计算最大时间
        for (int[] row : grid) {
            for (int val : row) {
                if (val == 1) return -1;
                ans = Math.max(ans, val);
            }
        }

        // 处理全腐烂或无橘子的情况
        return ans == 0 ? 0 : ans - 2;
    }

    public int orangesRotting2(int[][] grid) {
        int m = grid.length, n = grid[0].length;
        int ans = 0, fresh = 0;
        int[][] dirs = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
        Queue<int[]> queue = new ArrayDeque<>();
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == 2) {
                    queue.offer(new int[]{i, j});
                } else if (grid[i][j] == 1) {
                    fresh++;
                }
            }
        }
        while (fresh > 0 && !queue.isEmpty()) {
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                int[] cur = queue.poll();
                for (int[] dir : dirs) {
                    int x = cur[0] + dir[0];
                    int y = cur[1] + dir[1];
                    if (x >= 0 && x < m && y >= 0 && y < n && grid[x][y] == 1) {
                        grid[x][y] = 2;
                        fresh--;
                        queue.offer(new int[]{x, y});
                    }
                }
            }
            ans++;
        }
        return fresh == 0 ? ans : -1;
    }

    /**
     * 207. 课程表 <a href="https://leetcode.cn/problems/course-schedule/">...</a>
     * 难度： 中等
     * tags: 拓扑排序、图、广度优先搜索、数组、矩阵
     * description: 你这个学期必须选修 numCourses 门课程，记为  0  到  numCourses - 1 。
     * 在选修某些课程之前需要一些先修课程。 先修课程按数组  prerequisites 给出，其中  prerequisites[i] = [ai, bi] ，表示
     * 如果想选  course[i] ，则必须先选  course[bi] 。
     * 例如，先修课程对  [0, 1] 表示：想要学习课程 0 ，你需要先完成课程 1 。
     * 请你判断是否可能完成所有课程的学习？如果可以，返回 true ；否则，返回 false 。
     * restrictions:
     * 1 <= numCourses <= 2000
     * 0 <= prerequisites.length <= 5000
     * prerequisites[i].length == 2
     * 0 <= ai, bi < numCourses
     * 所有课程 互不相同
     * prerequisites[i] 中的所有课程 互不相同
     *
     * @param numCourses    课程数量
     * @param prerequisites 先修课程
     * @return 是否可能完成所有课程的学习
     * @see <a href="https://leetcode.cn/problems/course-schedule/">207. 课程表</a>
     */
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        ArrayList<ArrayList<Integer>> g = new ArrayList<>(numCourses);
        for (int i = 0; i < numCourses; i++) {
            g.add(new ArrayList<>());
        }
        for (int[] p : prerequisites) {
            g.get(p[1]).add(p[0]);
        }
        int[] state = new int[numCourses];
        for (int i = 0; i < numCourses; i++) {
            if (state[i] == 0 && canFinishdfs(g, state, i)) {
                return false;
            }
        }
        return true;
    }

    private boolean canFinishdfs(ArrayList<ArrayList<Integer>> g, int[] state, int i) {
        state[i] = 1;
        for (int j : g.get(i)) {
            if (state[j] == 1 || state[j] == 0 && canFinishdfs(g, state, j)) {
                return true;
            }
        }
        state[i] = 2;
        return false;
    }

    /**
     * 39. 组合总和 <a href="https://leetcode.cn/problems/combination-sum/">...</a>
     * tag: 动态规划 回溯
     * description: 给定一个候选人编号的数组 candidates （其中每个数都是唯一的）和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。
     * candidates 中的数字可以无限制重复被选取。
     * 说明：
     * 所有数字（包括目标数）都是正整数。
     * 解集不能包含重复的组合。
     * restriction:
     * 1 <= candidates.length <= 30
     * 1 <= candidates[i] <= 200
     *
     * @param candidates 候选人编号的数组
     * @param target     目标数
     * @return List<List < Integer>> 组合总和
     * @apiNote 1. 思路：动态规划 回溯
     * @see <a href="https://leetcode.cn/problems/combination-sum/">39. 组合总和</a>
     */
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        List<List<Integer>> ans = new ArrayList<>();
        List<Integer> path = new ArrayList<>();
        Arrays.sort(candidates);
        combinationSumdfs(ans, path, candidates, target, 0);
        return ans;
    }

    private void combinationSumdfs(List<List<Integer>> ans, List<Integer> path, int[] candidates, int left, int i) {
        if (left == 0) {
            ans.add(new ArrayList<>(path));
            return;
        }
        if (i == candidates.length - 1 || left < candidates[i]) {
            return;
        }

        combinationSumdfs(ans, path, candidates, left, i + 1);

        path.add(candidates[i]);
        combinationSumdfs(ans, path, candidates, left - candidates[i], i);
        path.removeLast();

//        // 枚举选哪个
//        for (int j = i; j < candidates.length; j++) {
//            path.add(candidates[j]);
//            dfs(j, left - candidates[j], candidates, ans, path);
//            path.remove(path.size() - 1); // 恢复现场
//        }

    }

    /**
     * 79. 单词搜索 <a href="https://leetcode.cn/problems/word-search/">...</a>
     * 难度： 中等
     * tags: 数组、哈希表、回溯、矩阵
     * description: 给定一个 m x n 二维字符网格 board 和一个字符串单词 word 。如果 word 存在于网格中，返回 true ；否则，返回 false 。
     * 单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。
     * restrictions:
     * m == board.length
     * n == board[i].length
     * 1 <= m, n <= 6
     * 1 <= word.length <= 15
     * board 和 word 仅由大小写英文字母组成
     * 进阶：你可以使用搜索剪枝，并允许重复使用字符，找到所有存在单词路径的单元格并返回 true 吗？
     *
     * @param board 二维字符网格
     * @param word  单词
     * @return 是否存在单词
     */
    public boolean exist(char[][] board, String word) {
        int n = board.length;
        int m = board[0].length;
        if (word.length() > m * n) {
            return false;
        }
        int[] count = new int[128];
        int[] wordCount = new int[128];
        for (char[] chars : board) {
            for (int j = 0; j < m; j++) {
                count[chars[j]]++;
            }
        }
        char[] w = word.toCharArray();
        for (char c : w) {
            wordCount[c]++;
            if (wordCount[c] > count[c]) {
                return false;
            }
        }
        if (count[word.charAt(0)] > count[word.charAt(word.length() - 1)]) {
            w = new char[word.length()];
            for (int i = 0; i < word.length(); i++) {
                w[word.length() - 1 - i] = word.charAt(i);
            }
            word = new String(w);
        }
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (board[i][j] == word.charAt(0) && existdfs(board, i, j, word, 0)) {
                    return true;
                }
            }
        }
        return false;
    }

    private boolean existdfs(char[][] board, int i, int j, String word, int index) {
        board[i][j] = 0;
        if (index == word.length() - 1) {
            return true;
        }
        int[][] dirs = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
        for (int[] dir : dirs) {
            int x = i + dir[0];
            int y = j + dir[1];
            if (x >= 0 && x < board.length && y >= 0 && y < board[0].length && board[x][y] != 0 && board[x][y] == word.charAt(index + 1) && existdfs(board, x, y, word, index + 1)) {
                return true;
            }
        }
        board[i][j] = word.charAt(index);
        return false;
    }


    /**
     * 51. N皇后 <a href="https://leetcode.cn/problems/n-queens/">...</a>
     * 难度：困难
     * tags: 回溯、位运算、矩阵
     * description: n 皇后问题研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。
     * 给定一个整数 n，返回所有不同的n皇后问题 的解决方案。
     * 每个解决方案包含一个明确的n 皇后问题的棋子放置方案，该方案中 'Q' 和 '.' 分别表示一个女王和空位。
     * restrictions:
     * 皇后可以攻击同一行、同一列、同一斜线，但不能攻击到其他皇后。
     *
     * @param n 皇后数量
     * @return 皇后问题解决方案
     */
    public List<List<String>> solveNQueens(int n) {
        List<List<String>> ans = new ArrayList<>();
        char[][] board = new char[n][n];
        for (char[] chars : board) {
            Arrays.fill(chars, '.');
        }
        int[] positions = new int[n];
        Arrays.fill(positions, -1);
        solveNQueensdfs(board, 0, positions, ans);
        return ans;
    }

    private void solveNQueensdfs(char[][] board, int index, int[] positions, List<List<String>> ans) {
        if (index == board.length) {
            List<String> path = new ArrayList<>();
            for (char[] chars : board) {
                path.add(new String(chars));
            }
            ans.add(path);
            return;
        }
        for (int i = 0; i < board.length; i++) {
            if (checkQueens(positions, index, i)) {
                board[index][i] = 'Q';
                positions[index] = i;
                solveNQueensdfs(board, index + 1, positions, ans);
                board[index][i] = '.';
                positions[index] = -1;
            }
        }
    }

    private boolean checkQueens(int[] positions, int index, int col) {
        for (int i = 0; i < index; i++) {
            if (positions[i] == col || Math.abs(positions[i] - col) == index - i) {
                return false;
            }
        }
        return true;
    }

    /**
     * 2359. 找到离给定节点最近的节点 <a href="https://leetcode.cn/problems/find-closest-node-to-given-two-nodes/">...</a>
     * 难度：中等
     * tags: 树、深度优先搜索、图
     * description: 给你一个 n 个节点的 有向图 ，节点编号为 0 到 n - 1 ，每个节点 至多 有一条出边。
     * 有向图用大小为 n 下标从 0 开始的数组 edges 表示，表示节点 i 有一条有向边指向 edges[i] 。如果节点 i 没有出边，那么 edges[i] == -1 。
     * 同时给你两个节点 node1 和 node2 。
     * 请你返回一个从 node1 和 node2 都能到达节点的编号，使节点 node1 和节点 node2 到这个节点的距离 较大值最小化。如果有多个答案，请返回 最小 的节点编号。如果答案不存在，返回 -1 。
     * 注意 edges 可能包含环。
     * restrictions:
     * n == edges.length
     * 2 <= n <= 10^5
     * -1 <= edges[i] < n
     * edges[i] != i
     * 0 <= node1, node2 < n
     *
     * @param edges 有向图
     * @param node1 节点1
     * @param node2 节点2
     * @return 最小距离的节点编号
     */
    public int closestMeetingNode(int[] edges, int node1, int node2) {
        int n = edges.length;
        boolean[] visited1 = new boolean[n];
        boolean[] visited2 = new boolean[n];
        int ans = n;
        while (node1 >= 0 || node2 >= 0) {
            if (node1 >= 0) {
                if (visited2[node1]) {
                    ans = node1;
                } else if (visited1[node1]) {
                    node1 = -1;
                } else {
                    visited1[node1] = true;
                    node1 = edges[node1];
                }
            }
            if (node2 >= 0) {
                if (visited1[node2]) {
                    ans = Math.min(ans, node2);
                } else if (visited2[node2]) {
                    node2 = -1;
                } else {
                    visited2[node2] = true;
                    node2 = edges[node2];
                }
            }
            if (ans < n) {
                return ans;
            }
        }
        return -1;

    }


    /**
     * 1298.你能从盒子里获得的最大糖果数 <a href="https://leetcode.cn/problems/maximum-candies-you-can-get-from-boxes/description">...</a>
     * 难度：中等
     * tags: 树、广度优先搜索、图
     * description: 有 n 个盒子，每个盒子的格式为 [status, candies, keys, containedBoxes] ，其中：
     * 状态字 status[i]：整数，如果 box[i] 是开的，那么是 1 ，否则是 0 。
     * 糖果数 candies[i]: 整数，表示 box[i] 中糖果的数目。
     * 钥匙 keys[i]：数组，表示你打开 box[i] 后，可以得到一些盒子的钥匙，每个元素分别为该钥匙对应盒子的下标。
     * 内含的盒子 containedBoxes[i]：整数，表示放在 box[i] 里的盒子所对应的下标。
     * 给你一个 initialBoxes 数组，表示你现在得到的盒子，你可以获得里面的糖果，也可以用盒子里的钥匙打开新的盒子，还可以继续探索从这个盒子里找到的其他盒子。
     * 请你按照上述规则，返回可以获得糖果的 最大数目 。
     * restrictions:
     * 1 <= status.length <= 1000
     * status.length == candies.length == keys.length == containedBoxes.length == n
     * status[i] 要么是 0 要么是 1 。
     * 1 <= candies[i] <= 1000
     * 0 <= keys[i].length <= status.length
     * 0 <= keys[i][j] < status.length
     * keys[i] 中的值都是互不相同的。
     * 0 <= containedBoxes[i].length <= status.length
     * 0 <= containedBoxes[i][j] < status.length
     * containedBoxes[i] 中的值都是互不相同的。
     * 每个盒子最多被一个盒子包含。
     * 0 <= initialBoxes.length <= status.length
     * 0 <= initialBoxes[i] < status.length
     *
     * @param status         状态
     * @param candies        糖果数
     * @param keys           钥匙
     * @param containedBoxes 内含的盒子
     * @param initialBoxes   初始盒子
     * @return 最大糖果数
     */
    public int maxCandies(int[] status, int[] candies, int[][] keys, int[][] containedBoxes, int[] initialBoxes) {
        int ans = 0;
        int n = status.length;
        // 盒子是否被打开过
        boolean[] visit = new boolean[n];
        // 可以打开的盒子队列
        Deque<Integer> open = new ArrayDeque<>();
        // 获得过的盒子
        HashSet<Integer> get = new HashSet<>();
        // 初始入队
        for (int i : initialBoxes) {
            get.add(i);
            if (status[i] == 1) {
                open.offerLast(i);
            }
        }
        while (!open.isEmpty()) {
            int top = open.removeFirst();
            visit[top] = true;
            for (int i : keys[top]) {
                if (status[i] == 0 && get.contains(i)) {
                    open.offerLast(i);
                }
                status[i] = 1;
            }
            for (int i : containedBoxes[top]) {
                get.add(i);
                if (status[i] == 1 && !visit[i]) {
                    open.offerLast(i);
                }
            }
        }
        for (int i = 0; i < n; i++) {
            if (status[i] == 1 && get.contains(i)) {
                ans += candies[i];
            }
        }
        return ans;
    }
}
